import java.util.*;

/**
 * @author LKQ
 * @date 2022/5/9 22:38
 * @description 考验抽象能力，将题目抽象为多维背包问题，每个字符串的价值都是1（对于答案的贡献为1），选择的成本为字符串中1的数量和0的数量
 * 相当于 1不超过m, 0不超过 n的情况下，最大价值是多少。
 *
 */
public class Solution {
    public static void main(String[] args) {

    }
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        // 统计每个字符串中，0的个数和1的个数
        int[][] cnt = new int[len][2];
        for (int i = 0; i < len; i++) {
            String str = strs[i];
            int zero = 0, one = 0;
            for (char c : str.toCharArray()) {
                if (c == '0') zero++;
                else one++;

            }
            cnt[i] = new int[]{zero, one};
        }
        // 代表考虑前 k 件物品，在数字 1 容量不超过 i，数字 0 容量不超过 j 的条件下的「最大价值」（每个字符串的价值均为 1）。
        int[][][] f = new int[len + 1][m + 1][n + 1];
        for (int k = 1; k <= len; k++) {
            // 第k件物品的 0的数量 和 1的数量
            int zero = cnt[k - 1][0], one = cnt[k - 1][1];
            for (int i = 0; i <= m; i++) {
                for (int j = 0; j <= n; j++) {
                    // 不选择第k件物品
                    int a = f[k - 1][i][j];
                    // 选择第K件物品
                    int b = (i >= zero && j >= one) ? f[k - 1][i - zero][j - one] + 1 : 0;
                    f[k][i][j] = Math.max(a, b);
                }
            }
        }
        return f[len][m][n];
    }
}
